/*
题目: 整数拆分
给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

https://leetcode.cn/problems/integer-break/
 */
public class IntegerBreak {
    public int integerBreak(int n) {
        // 表示整数 i 拆分的最大 乘积
        int[] dp = new int[n + 1];
        // 初始化: 这些整数的乘积 起码 不拆比较大
        dp[1] = 1;

        // 就 [该整数] 进行拆分
        for (int i = 2; i <= n; i ++) {
            // 各种 [拆分方法], 拆完后, 最终选择一个最大的
            int maxn = 0;
            for (int j = 1; j < i; j ++) {
                maxn = Math.max(maxn, Math.max(j * (i - j), j * dp[i - j]));
            }
            dp[i] = maxn;
        }

        return dp[n];
    }
}
